package cc.magicjson.example.demo.tsp;

import java.util.*;

public class GeneticTSP {
    private int[][] dist; // 距离矩阵
    private int n; // 城市数量
    private int populationSize; // 种群大小
    private double mutationRate; // 变异率
    private int generations; // 进化的代数

    public GeneticTSP(int[][] dist, int populationSize, double mutationRate, int generations) {
        this.dist = dist; // 初始化距离矩阵
        this.n = dist.length; // 初始化城市数量
        this.populationSize = populationSize; // 初始化种群大小
        this.mutationRate = mutationRate; // 初始化变异率
        this.generations = generations; // 初始化进化代数
    }

    // 生成初始种群，种群中每个个体代表一个城市的访问顺序（路径）
    private List<int[]> generateInitialPopulation() {
        List<int[]> population = new ArrayList<>();
        for (int i = 0; i < populationSize; i++) {
            int[] tour = new int[n]; // 初始化路径
            for (int j = 0; j < n; j++) {
                tour[j] = j; // 初始路径为顺序访问每个城市
            }
            shuffleArray(tour); // 打乱路径顺序，生成一个随机的初始解
            population.add(tour); // 将路径添加到种群中
        }
        return population;
    }

    // 打乱数组顺序，用于生成随机路径
    private void shuffleArray(int[] array) {
        Random rand = new Random();
        for (int i = array.length - 1; i > 0; i--) {
            int index = rand.nextInt(i + 1); // 随机选择一个索引
            int temp = array[index]; // 交换元素
            array[index] = array[i];
            array[i] = temp;
        }
    }

    // 计算一条路径的总距离
    private int calculateTotalDistance(int[] tour) {
        int length = 0; // 初始化路径长度
        for (int i = 0; i < n - 1; i++) {
            length += dist[tour[i]][tour[i + 1]]; // 累加路径中相邻城市间的距离
        }
        length += dist[tour[n - 1]][tour[0]]; // 回到起点的距离
        return length; // 返回总路径长度
    }

    // 随机选择父代个体，轮盘赌选择或随机选择
    private int[] selectParent(List<int[]> population) {
        Random rand = new Random();
        return population.get(rand.nextInt(populationSize)); // 随机选择种群中的一个个体作为父代
    }

    // 交叉操作，用两个父代生成一个子代
    private int[] crossover(int[] parent1, int[] parent2) {
        int[] child = new int[n]; // 初始化子代路径
        Arrays.fill(child, -1); // 将子代路径初始化为-1，表示未确定的城市
        Random rand = new Random();
        int startPos = rand.nextInt(n); // 随机选择交叉起始点
        int endPos = rand.nextInt(n); // 随机选择交叉结束点

        // 确保起始点在结束点之前
        if (startPos > endPos) {
            int temp = startPos;
            startPos = endPos;
            endPos = temp;
        }

        // 将父代1的部分基因复制到子代中
        for (int i = startPos; i <= endPos; i++) {
            child[i] = parent1[i];
        }

        // 从父代2中填补子代中剩余的未确定城市
        for (int i = 0; i < n; i++) {
            if (!contains(child, parent2[i])) { // 如果父代2的城市不在子代中
                for (int j = 0; j < n; j++) {
                    if (child[j] == -1) { // 找到子代中第一个未确定的位置
                        child[j] = parent2[i]; // 填入父代2的城市
                        break;
                    }
                }
            }
        }
        return child; // 返回生成的子代
    }

    // 检查数组中是否包含某个元素
    private boolean contains(int[] array, int value) {
        for (int i : array) {
            if (i == value) { // 如果找到目标值
                return true;
            }
        }
        return false;
    }

    // 变异操作，通过交换路径中的两个城市位置来实现
    private void mutate(int[] tour) {
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            if (rand.nextDouble() < mutationRate) { // 如果随机数小于变异率
                int j = rand.nextInt(n); // 随机选择另一个城市
                int temp = tour[i]; // 交换这两个城市的位置
                tour[i] = tour[j];
                tour[j] = temp;
            }
        }
    }

    // 遗传算法求解TSP问题
    public int findShortestPath() {
        List<int[]> population = generateInitialPopulation(); // 生成初始种群
        int[] bestTour = population.get(0); // 初始化最优路径为种群中的第一个个体
        int bestDistance = calculateTotalDistance(bestTour); // 计算最优路径的长度

        // 迭代进行遗传算法进化
        for (int generation = 0; generation < generations; generation++) {
            List<int[]> newPopulation = new ArrayList<>(); // 创建新种群
            for (int i = 0; i < populationSize; i++) {
                int[] parent1 = selectParent(population); // 选择第一个父代
                int[] parent2 = selectParent(population); // 选择第二个父代
                int[] child = crossover(parent1, parent2); // 交叉生成子代
                mutate(child); // 进行变异
                newPopulation.add(child); // 将子代加入新种群

                int childDistance = calculateTotalDistance(child); // 计算子代的路径长度
                if (childDistance < bestDistance) { // 如果子代路径优于当前最优路径
                    bestDistance = childDistance; // 更新最优路径
                    bestTour = child; // 更新最优路径对应的城市顺序
                }
            }
            population = newPopulation; // 更新种群为新种群
        }
        return bestDistance; // 返回最优路径的长度
    }

    public static void main(String[] args) {
        int[][] dist = {
                {0, 10, 15, 20},  // 城市间的距离矩阵
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };

        GeneticTSP geneticTSP = new GeneticTSP(dist, 100, 0.01, 500); // 创建遗传算法实例
        System.out.println("遗传算法计算的路径长度: " + geneticTSP.findShortestPath()); // 输出计算结果
    }
}
